//import org.junit.Test;
//import java.util.ArrayList;
//import java.util.List;
//import java.util.Random;
//import static org.junit.Assert.assertEquals;
//
//public class KDTreeTest {
//    private static Random R = new Random(500);
//
//    public static List<point> pointList() {
//        point p1 = new point(2, 3); // constructs a point with x = 1.1, y = 2.2
//        point p2 = new point(4, 2);
//        point p22 = new point(4, 2);
//        point p3 = new point(4, 5);
//        point p4 = new point(3, 3);
//        point p5 = new point(1, 5);
//        point p6 = new point(4, 4);
//        return List.of(p1, p2, p22, p3, p4, p5, p6);
//    }
//
//    public static KDTree buildLectureTree() {
//        KDTree kdTree = new KDTree(pointList());
//        return kdTree;
//    }
//
//    public static NaivePointSet naivePointSetTest() {
//        NaivePointSet naivePointSet = new NaivePointSet(pointList());
//        return naivePointSet;
//    }
//
//    @Test
//    /** test code by using examples from the nearest slides **/
//    public void testNearestDemoSlides() {
//        KDTree kd = buildLectureTree();
//        NaivePointSet naivePointSet = naivePointSetTest();
//        point actual = kd.nearest(0, 7);
//        point expect = naivePointSet.nearest(0, 7);
//        assertEquals(expect, actual);
//    }
//
//    /**
//     * https://www.youtube.com/watch?v=lp80raQvE5c
//     */
//    @Test
//    public void startWith1000Points200Queries() {
//        int PointCount = 1000;
//        int QueryCount = 200;
//        startWithNPointsMQueries(PointCount, QueryCount);
//    }
//
//    private void startWithNPointsMQueries(int PointCount, int QueryCount) {
//        List<point> points = randomPoints(PointCount);
//        KDTree kdTree = new KDTree(points);
//        NaivePointSet naivePointSet = new NaivePointSet(points);
//
//        List<point> queries = randomPoints(QueryCount);
//        for (point p : queries) {
//            point expected = naivePointSet.nearest(p.getX(), p.getY());
//            point actual = kdTree.nearest(p.getX(), p.getY());
//            assertEquals(expected, actual);
//        }
//    }
//
//    private point randomPoint() {
//        double x = R.nextDouble();
//        double y = R.nextDouble();
//        return new point(x, y);
//    }
//
//    // return N random points
//    private List<point> randomPoints(int N) {
//        List<point> points = new ArrayList<>();
//        for (int i = 0; i <= N; i++) {
//            points.add(randomPoint());
//        }
//        return points;
//    }
//
//    @Test
//    public void timeTest() {
//        List<point> randomPoints = randomPoints(100000);
//        KDTree kd = new KDTree(randomPoints);
//        NaivePointSet nps = new NaivePointSet(randomPoints);
//        List<point> queryPoints = randomPoints(10000);
//
//        long start = System.currentTimeMillis();
//        for (point point : queryPoints) {
//            nps.nearest(point.getX(), point.getY());
//        }
//        long end = System.currentTimeMillis();
//        System.out.println("After 10000 queries, NaivePointSet spends " + (end - start) + " time.");
//
//        start = System.currentTimeMillis();
//        for (point point : queryPoints) {
//            kd.nearest(point.getX(), point.getY());
//        }
//        end = System.currentTimeMillis();
//        System.out.println("After 10000 queries, kd spends " + (end - start) + " time.");
//
//    }
//
//
//}
////    public static void main(String[] args) {
//////        jh61b.junit.TestRunner.runTests(KDTreeTest.class);
////    }